package solution;

import solution.util.TreeNode;

/**
 * <a href="https://www.nowcoder.com/study/live/717/2/10">
 * 第10节 课后作业1-检查是否为BST</a>
 *
 * @author or2
 * @Description 现给定树的根结点指针TreeNode* root，编辑函数返回一个bool值，判断该树是否为二叉查找树。
 * @create 2021年09月16日 时间: 11:05
 */
public class CheckBST {
    public boolean checkBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        return checkBST(root.left, Integer.MIN_VALUE, root.val) && checkBST(root.right, root.val, Integer.MAX_VALUE);
    }

    /**
     * 通过数值区间检测BST
     *
     * @param root       当前结点
     * @param leftBound  当前结点左子树取值范围
     * @param rightBound 当前结点右子树取值范围
     * @return 是BST? true: false;
     */
    private boolean checkBST(TreeNode root, int leftBound, int rightBound) {
        if (root == null) {
            return true;
        }

        if (root.left != null) {
            if (root.left.val > root.val || root.left.val < leftBound)
                return false;
        }
        if (root.right != null) {
            if (root.right.val < root.val || root.right.val > rightBound)
                return false;
        }

        return checkBST(root.left, leftBound, root.val) && checkBST(root.right, root.val, rightBound);
    }
}
